int dep[N] , sz[N] , hson[N];
int fa[N] , tp[N] , dfn[N] , dfn_id[N] , tot;
void dfs1(int u , int far)
{
	sz[u] = 1 , fa[u] = far;
	dep[u] = dep[far] + 1; 
	for(int i = head[u] ; i ; i = edge[i].nex)
	{
		int v = edge[i].to;
		if(v == far) continue ;		
		dfs1(v , u);
		sz[u] += sz[v];
		if(sz[v] > sz[hson[u]]) hson[u] = v;
 	}
} 
void dfs2(int u , int far , int top)
{
	tp[u] = top;
	dfn[u] = ++ tot;
	dfn_id[tot] = u; 
	if(!hson[u]) return ;
	dfs2(hson[u] , u , top);
	for(int i = head[u] ; i ; i = edge[i].nex)
	{
		int v = edge[i].to;
		if(v == far || v == hson[u]) continue ;
		dfs2(v , u , v);
	}
}
int get_far(int x , int k)
{
	if(!k) return x;
	int t = dep[x] - k;
	if(t <= 0) return 0;
	while(dep[tp[x]] > t) x = fa[tp[x]];
	t = dep[x] - t;
	return dfn_id[dfn[x] - t];
}
